package one.chapter_2;

import edu.princeton.cs.algs4.StdRandom;

public class QuickSort extends AbstractSort {


    protected void sort(Comparable[] a) {
        StdRandom.shuffle(a);
        sort(a,0,a.length-1);
    }

    private void sort(Comparable[] a, int lo, int hi) {
        if (hi<=lo){
            int j=partition(a,lo,hi);
            sort(a,lo,j-1);
            sort(a,j+1,hi);
        }
    }

    private int partition(Comparable[] a, int lo, int hi) {
        int i=lo;
        int j=hi+1;
        Comparable v=a[lo];
        while (true){
            //首先从lo一直到hi遍历找到v>a[++i]，然后从hi一直到lo遍历找到a[--j]<v  找到后将i,j的元素交换位置
            while (less(a[++i],v)){
                //不用交换元素，
                if (i==hi){
                    break;
                }
            }

            while (less(v,a[--j])){
                if (j==lo){
                    break;
                }
            }
            if (i>=j){
                break;
            }
            exch(a,i,j);
        }
        exch(a,lo,j);

        return j;
    }
}
